package de.riceman.simpleGo.main;
import java.util.AbstractSet;
import java.util.HashSet;
import java.util.Iterator;
import javax.activation.UnsupportedDataTypeException;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import de.riceman.simpleGo.exceptions.IllegalMoveException;



/**
 * The class Configuration.
 * This class holds all basic information on a Go board, its current status,
 * and provides methods to perform a valid move.
 * 
 * @author Mario Reissmann
 */
public class Configuration implements Cloneable {

	private static final Log logger = LogFactory.getLog(Configuration.class);
	
	/** The size, i.e. the number of rows or columns of the board. */
	private int size;
	
	/** The adjacency matrix. */
	private BitMatrix adjacencies;
	
	/** The set of dark stones. */
	private BitMatrix dark;
	
	/** The set of light stones. */
	private BitMatrix light;
	
	/** The dark partitions. */
	private AbstractSet<BitMatrix> darkPartitions;
	
	/** The light partitions. */
	private AbstractSet<BitMatrix> lightPartitions;
	
	/** The clear partitions. */
	private AbstractSet<BitMatrix> clearPartitions;
	
	/** The dark player's captured partitions. */
	private AbstractSet<BitMatrix> darksCapturedPartitions;

	/** The light player's captured partitions. */
	private AbstractSet<BitMatrix> lightsCapturedPartitions;
	
	/** The number of the dark player's captured stones. */
	private int darksCaptured;
	
	/** The number of the light player's captured nodes. */
	private int lightsCaptured;
	
	/** The number of the dark player's dead stones removed from the board. */
	private int darksDeadStones;

	/** The number of the light player's dead stones removed from the board. */
	private int lightsDeadStones;
	
	/** The players turn. True for dark's, false for light's. */
	private boolean playersTurn;
	
	/** The BitMatrix holding the set of regular moves. */
	private BitMatrix regularMoves;
	
	/** A change pointer. True if a move has been performed
	 * since the regular moves were computed the last time,
	 * otherwise false. */
	private boolean regularMovesChanged;
	
	/** The position table used to prevent superko repetitions. */
	private PositionTable history;
	
	/** If set to true, this is not the configuration of the
	 * game and some logging may be prevented. */
	private boolean isclone = false;

	/**
	 * The constructor. Creates a configuration object.
	 * 
	 * @param size The number of rows or columns of the board.
	 */
	public Configuration(int size) {

		this.size = size;
		dark = new BitMatrix(1, size*size);
		light = new BitMatrix(1, size*size);
		
		darkPartitions = new HashSet<BitMatrix>();
		lightPartitions = new HashSet<BitMatrix>();
		clearPartitions = new HashSet<BitMatrix>();
		//Add a clear partition since the board is empty.
		clearPartitions.add(BitMatrix.not(new BitMatrix(1, size*size)));
		
		darksCapturedPartitions = new HashSet<BitMatrix>();
		lightsCapturedPartitions = new HashSet<BitMatrix>();
		
		//Create the adjacency matrix.
		adjacencies = initAdjacencyMatrix(size);
		
		history = new PositionTable();
		
		//Dark moves first.
		playersTurn = true;
		
		//The regularMoves BitMatrix needs to be initialized.
		regularMoves = new BitMatrix(1, size*size);
		regularMovesChanged = true;
		
		//Nothing captured so far.
		darksCaptured = 0;
		lightsCaptured = 0;
	}

	/**
	 * Initializes the adjacency matrix.
	 * 
	 * @param size The number of rows or columns of the board.
	 * 
	 * @return The adjacency matrix.
	 */
	private BitMatrix initAdjacencyMatrix(int size) {
	
		BitMatrix adjacencies = new BitMatrix(size*size);
				
		for (int i = 0; i < (size*size); i++) {
			//Each vertex of the graph is connected to itself.
			adjacencies.set(i, i, true);
			
			//Connect the current vertex to its left neighbour,
			//if it's not located in the first column.
			if ((i%size) != 0) {
				adjacencies.set(i, i-1, true);
				//The adjacency matrix is symmetric with respect
				//to its diagonal.
				adjacencies.set(i-1, i, true);
			}
			
			//Connect the current vertex to its bottom neighbour,
			//if it's not located in the last row.
			if (i < size*(size-1)) {
				adjacencies.set(i, i+size, true);
				adjacencies.set(i+size, i, true);
			}
		}
		
		return adjacencies;
	}
	
	/**
	 * Expands adjacent groups after a move.
	 * 
	 * @param move The move as BitMatrix.
	 * @param player True if dark, false if light.
	 */
	private void expandPartitions(BitMatrix move, boolean player) {
		
		Iterator<BitMatrix> it;
		
		AbstractSet<BitMatrix> hs;
		
		BitMatrix s;
		
		if (player) {
			hs = darkPartitions;
		} else {
			hs = lightPartitions;
		}
		
		it = hs.iterator();
		
		try {
			//Iterate the player's groups...
			while (it.hasNext()) {
				s = (BitMatrix) it.next();

				//...and search for adjacent groups.
				if (BitMatrix.isConnected(move, s, adjacencies)) {
					
					//Merge move with the adjacent group and remove it.
					move = BitMatrix.union(move, s);
					it.remove();
				}
			}
			//Add move, now containing all connected groups or just the move.
			hs.add(move);
		} catch (UnsupportedDataTypeException e) {
			e.printStackTrace();
		}
	}
	
	/**
	 * Expands the clear partition the move belonged to before.
	 * The affected partition will be reduced by the move,
	 * and split up into several clear partitions if necessary.
	 * 
	 * @param move The move as BitMatrix.
	 * @param player True if dark, false if light.
	 */
	private void expandClearPartitions(BitMatrix move, boolean player) {

		Iterator<BitMatrix> clearPartitionIterator;
		
		BitMatrix s, t;

		clearPartitionIterator = clearPartitions.iterator();
		
		try {
			//Iterate all clear partitions.
			while (clearPartitionIterator.hasNext()) {
				s = (BitMatrix) clearPartitionIterator.next();
				
				//Find the clear partition the stone has been set into.
				if (s.intersects(move)) {

					//Remove the clear partition from the set.
					clearPartitionIterator.remove();
					//Remove the set stone from the clear partition.
					s.remove(move);
					
					//Now split the clear partition if necessary.
					
					//While the partition still contains more than one clear vertex...
					while (!s.isZeroMatrix()) {
						//...create a BitSet for a random clear vertex.
						t = new BitMatrix(1, size*size);
						t.set(s.getIndexOfFirstSetBit());
						
						//Expand the partition's radius by one within the borders of the initial clear partition.
						BitMatrix u = BitMatrix.intersection(BitMatrix.multiply(t, adjacencies), s);
						BitMatrix v;
							
						//Loop until the subpartition got maximal.
						while(true) {
							//Try expanding the partition one more time...
							v = BitMatrix.intersection(BitMatrix.multiply(u, adjacencies), s);
							//...and check if it got any bigger.
							if (!u.equals(v)) {
								//If so, continue until the maximum size is reached.
								u = v;
							} else {
								//If the borders of the clear partition have been reached,
								//add the partition to the set of clear partitions.
								clearPartitions.add(u);
								
								/* Remove the clear partition from the initial one,
								 * for there may be more to add. If so, the outer while-loop
								 * will be executed once more. That means the move splits
								 * a clear partition into several parts. */
								s.remove(u);
								break;
							}
						}
					}
					
					//Stop searching if the initial clear partition is found.
					break;
				}	 	
			}
			
		} catch (UnsupportedDataTypeException e) {
			e.printStackTrace();
		}
	}
	
	/**
	 * Initializes the clear partitions of any position.
	 * This method is used if no incremental approach can be used.
	 * 
	 * @return The clear partitions as a set of BitMatrix objects.
	 */
	private AbstractSet<BitMatrix> initClearPartitions() {

		//The structure to store the clear partitions of the board.
		AbstractSet<BitMatrix> hs = new HashSet<BitMatrix>();
		
		Iterator<BitMatrix> it;
		
		BitMatrix r, s;
		int i;		
		
		try {
			//Create a BitSet for every clear place.
			for(i = 0; i < light.getColumns(); i++) {
				
				if (!light.get(0, i) && !dark.get(0, i)) {
					r = new BitMatrix(1, size*size);
					r.set(0, i, true);
					
					it = hs.iterator();
					
					while (it.hasNext()) {
						s = (BitMatrix) it.next();
						
						//Merge connected clear partitions.
						if (BitMatrix.isConnected(r, s, adjacencies)) {

							r = BitMatrix.union(r, s);
							it.remove();
						}
					}
					
					hs.add(r);
				}
			}
		
		} catch (UnsupportedDataTypeException e) {
			e.printStackTrace();
		}
		
		return hs;
	}
	
	/**
	 * Gets the total number of the specified player's liberties.
	 * 
	 * @param player True if dark, false if light.
	 * 
	 * @return The player's number of liberties.
	 */
	public int getLibertiesOfPlayer(boolean player) {
		
		int sum = 0;
		Iterator<BitMatrix> it;
		
		if (player) {
			it = darkPartitions.iterator();
		} else {
			it = lightPartitions.iterator();
		}
		
		while (it.hasNext()) {
			sum += this.getLibertiesOfPartition(it.next()).getNumberOfSetBits();
		}
		
		return sum;
	}
	
	/*
	 * Gets the liberties of the specified partition.
	 * 
	 * @param partition The partition as BitMatrix.
	 * 
	 * @return The liberties of the partition as BitMatrix.
	 */
	public BitMatrix getLibertiesOfPartition(BitMatrix partition) {
		
		BitMatrix b;
		
		try {
			//Get the surrounding vertices.
			b = BitMatrix.multiply(partition, adjacencies);
			b.xor(partition);

			//Remove all occupied vertices.
			b.remove(dark);
			b.remove(light);
			
			return b;
			
		} catch (UnsupportedDataTypeException e) {
			e.printStackTrace();
			return null;
		}
	}
	
	/**
	 * Checks for validity of the specified move and initiates its execution.
	 * 
	 * @param player True if dark, false if light.
	 * @param move The move as BitMatrix.
	 * 
	 * @throws UnsupportedDataTypeException The UnsupportedDataTypeException.
	 * @throws IllegalMoveException The IllegalMoveException.
	 */
	public void doMove(boolean player, BitMatrix move)
		throws UnsupportedDataTypeException, IllegalMoveException {
		
		//The move BitMatrix may be stored in an AbstractSet and modified later.
		//Create a clone to prevent corruption.
		move = (BitMatrix) move.clone();
		
		//Check if the move is valid.
		if (move.isZeroMatrix() || move.intersects(this.getRegularMoves(player))) {

			//If so, then actually execute the move.
			executeMove(player, move);
			
			//Add the current position to the position history to recognize superko situations.
			history.addPosition(dark, light, getPlayersTurn());
		} else {
			throw new IllegalMoveException("invalid move!");
		}
	}
	
	/**
	 * Performs the move.
	 * 
	 * @param player True if dark, false if light.
	 * @param move The move as a BitMatrix.
	 * @throws UnsupportedDataTypeException The UnsupportedDataTypeException.
	 */
	private void executeMove(boolean player, BitMatrix move)
		throws UnsupportedDataTypeException {
		
		BitMatrix b;
		
		if (player) {
			b = dark;
		} else {
			b = light;
		}
		
		//Check if move is a pass.
		int i = move.getIndexOfFirstSetBit();
		
		if (i > -1) {
			
			//Add the move to the player's set of stones.
			b.set(i);
			
			//Expand the player's adjacent groups.
			this.expandPartitions(move, player);

			//Delete opponent's adjacent groups with 0 liberties and add them to the set of clear partitions.
			//They'll be classified as real or non-real eyes in assignCapturedPartitions().
			this.clearCaptured(!player);
			
			//Expand the clear partitions.
			this.expandClearPartitions(move, player);

			//Assign clear partitions to capturing player.
			this.assignCapturedPartitions();
			
			/*if (!isclone) {
				System.out.println("dark stones:");
				System.out.println(dark.toString());
				System.out.println("light stones:");
				System.out.println(light.toString());
				
				System.out.println("dark partitions:");
				Iterator<BitMatrix> it = darkPartitions.iterator();
				
				while (it.hasNext()) {
					System.out.println(it.next().toString());
				}
				
				System.out.println("light partitions:");
				it = lightPartitions.iterator();
				
				while (it.hasNext()) {
					System.out.println(it.next().toString());
				}
				
				System.out.println("clear partitions:");
				it = clearPartitions.iterator();
				
				while (it.hasNext()) {
					System.out.println(it.next().toString());
				}
				
				System.out.println("darks captured partitions (unreal eyes):");
				it = darksCapturedPartitions.iterator();
				
				while (it.hasNext()) {
					System.out.println(it.next().toString());
				}
	
				System.out.println("lights captured partitions (unreal eyes):");
				it = lightsCapturedPartitions.iterator();
				
				while (it.hasNext()) {
					System.out.println(it.next().toString());
				}
			}*/
		}
		
		changePlayersTurn();
		regularMovesChanged = true;
	}
	
	
	/**
	 * Assigns captured partitions to the owning player. This is not incremental yet
	 * and should be merged with the previous methods called after a move had been performed.
	 */
	private void assignCapturedPartitions() {
		Iterator<BitMatrix> it;
		BitMatrix clearPartition, surroundingNodes, playersSurroundingNodes, owningPartition;
		AbstractSet<BitMatrix> owningPartitions = new HashSet<BitMatrix>();
		
		//Clear the non-real eyes of both players.
		darksCapturedPartitions.clear();
		lightsCapturedPartitions.clear();
		
		//Clear the real eyes of both players.
		it = darkPartitions.iterator();
		
		while (it.hasNext()) {
			it.next().getChildren().clear();
		}
		
		it = lightPartitions.iterator();
		
		while (it.hasNext()) {
			it.next().getChildren().clear();
		}
		
		//Iterate the clear partitions.
		it = clearPartitions.iterator();
		
		while (it.hasNext()) {
			clearPartition = it.next();
	
			//if (!isclone) {System.out.println("   clearPartition: " + clearPartition.toString());}
			try {
				//Compute the surrounding stones of the current clear partition.
				surroundingNodes = BitMatrix.xor(
						BitMatrix.multiply(clearPartition, adjacencies),
						clearPartition);
				
				
				playersSurroundingNodes = BitMatrix.intersection(surroundingNodes, dark);
				
				//Check if the clear partition is completely surrounded by the dark player's stones.
				if (playersSurroundingNodes.equals(surroundingNodes)) {
					
					//Get all groups surrounding the clear partition.
					owningPartitions = getPartitionsForFraction(playersSurroundingNodes);
					
					//If it is only one, this is a real eye.
					if (owningPartitions.size() == 1) {
						//Assign the clear partition to the owning partition.
						owningPartition = owningPartitions.iterator().next();
						owningPartition.getChildren().add(clearPartition);
						//if (!isclone) System.out.println("   added dark real eye: " + clearPartition.toString());
					} else {
						//Clear partition is not a real eye. Assign the clear partition
						//to the player's set of captured partitions
						darksCapturedPartitions.add(clearPartition);
						//if (!isclone) System.out.println("   added dark non-real eye: " + clearPartition.toString());
					}
					//Clear partition remains in the set of clear partitions as well.
				} else { 
				
					//The same for light.
					playersSurroundingNodes = BitMatrix.intersection(surroundingNodes, light);
					
					if (playersSurroundingNodes.equals(surroundingNodes)) {
						
						owningPartitions = getPartitionsForFraction(playersSurroundingNodes);
						
						if (owningPartitions.size() == 1) {
							owningPartition = owningPartitions.iterator().next();
							owningPartition.getChildren().add(clearPartition);
							//if (!isclone) System.out.println("   added light real eye: " + clearPartition.toString());
						} else {
							lightsCapturedPartitions.add(clearPartition);
							//if (!isclone) System.out.println("   added light non-real eye: " + clearPartition.toString());
						}
					}
				}
				
			} catch (UnsupportedDataTypeException e) {
				e.printStackTrace();
				break;
			}
		}
	}
	
	
	/**
	 * Gets the group to which a single stone is already connected.
	 * 
	 * @param stone The stone as BitMatrix.
	 * 
	 * @return The group of the single stone.
	 * 
	 * @throws UnsupportedDataTypeException The UnsupportedDataTypeException.
	 */
	private BitMatrix getOwningPartitionForSingleStone (BitMatrix stone)
			throws UnsupportedDataTypeException {
		
		if (stone.getNumberOfSetBits() != 1) {
			throw new UnsupportedDataTypeException("getOwningPartitionForSingleStone() expects exactly one set Bit!");
		}
		
		BitMatrix a;
		Iterator<BitMatrix> it;
		
		it = darkPartitions.iterator();
		

		while (it.hasNext()) {
			a = it.next();

			if (a.intersects(stone)) {
				return a;
			}
		}
		
				
		it = lightPartitions.iterator();
		
		
		while (it.hasNext()) {
			a = it.next();

			if (a.intersects(stone)) {
				return a;
			}
		}
		
		return stone;
	}	
	
	/**
	 * Gets the group of the player to which a stone would belong if it was set.
	 * 
	 * @param move The move as BitMatrix.
	 * 
	 * @return The resulting group as BitMatrix.
	 *  
	 * @throws UnsupportedDataTypeException The UnsupportedDataTypeException.
	 */
	public BitMatrix getResultingPartitionForMove (boolean player, BitMatrix move)
			throws UnsupportedDataTypeException {

		if (move.getNumberOfSetBits() != 1) {
			throw new UnsupportedDataTypeException("getResultingPartitionForMove() expects exactly one set Bit!");
		}

		BitMatrix a, playersNextPartition, resultingPartition;

		Iterator<BitMatrix> it;
		
		//Expand the move's partition by one.
		a = BitMatrix.multiply(move, adjacencies);
		
		resultingPartition = (BitMatrix) move.clone();
		
		if (player) {
			it = darkPartitions.iterator();
		} else {
			it = lightPartitions.iterator();
		}

		//Get adjacent groups of the same player.
		while (it.hasNext()) {
			playersNextPartition = it.next();

			//If one is found...
			if (a.intersects(playersNextPartition)) {
				//...unify it with the group.
				resultingPartition.union(playersNextPartition);
			}
		}
		
		return resultingPartition;
	}
	
	
	/**
	 * Gets the adjacent groups of the opponent for the specified move.
	 * 
	 * @param player True if dark, false if light.
	 * @param move The move as BitMatrix.
	 * 
	 * @return The opponent's adjacent groups.
	 * 
	 * @throws UnsupportedDataTypeException The UnsupportedDataTypeException.
	 */
	private AbstractSet<BitMatrix> getOpponentsAdjacentPartitionsForMove (boolean player, BitMatrix move)
			throws UnsupportedDataTypeException {

		if (move.getNumberOfSetBits() != 1) {
			throw new UnsupportedDataTypeException("getOpponentsAdjacentPartitionsForMove() currently expects exactly one set Bit!");
		}
		
		AbstractSet<BitMatrix> adjacentPartitions = new HashSet<BitMatrix>();
		
		BitMatrix adjacentPositions, opponentsNextPartition;
		Iterator<BitMatrix> it;
				
		//Expand the move's partition by one.
		adjacentPositions = BitMatrix.multiply(move, adjacencies);
		
		if (player) {
			it = lightPartitions.iterator();
		} else {
			it = darkPartitions.iterator();
		}
		
		//Get adjacent groups of the opponent.
		while (it.hasNext()) {
			opponentsNextPartition = it.next();
			
			//If one is found...
			if (adjacentPositions.intersects(opponentsNextPartition)) {
				//...add it to the set of the opponent's adjacent groups.
				adjacentPartitions.add(opponentsNextPartition);
			}
		}
		
		return adjacentPartitions;
	}
	
	/**
	 * Returns true, if at least one of the groups has exactly one liberty.
	 * 
	 * @param partitions The set of groups.
	 * 
	 * @return True, if successful, otherwise false.
	 */
	private boolean containsPartitionWithExactlyOneLiberty(AbstractSet<BitMatrix> partitions) {
		
		Iterator<BitMatrix> it = partitions.iterator();
		
		while (it.hasNext()) {
			if (this.getLibertiesOfPartition(it.next()).getNumberOfSetBits() == 1) {
				return true;
			}
		}
		
		return false;
	}
	
	
	/**
	 * Gets the groups for a fraction of stones.
	 * 
	 * @param fraction The fraction as BitMatrix.
	 * 
	 * @return The groups in the fraction.
	 */
	private AbstractSet<BitMatrix> getPartitionsForFraction(BitMatrix fraction) {
		
		AbstractSet<BitMatrix> hs = new HashSet<BitMatrix>();
		BitMatrix a;
		
		Iterator<BitMatrix> it;
		
		it = darkPartitions.iterator();
		
		try {
			//Iterate the dark groups.
			while (it.hasNext()) {
				a = it.next();

				//If a dark group belongs to the fraction, add it to the result set.
				if (a.intersects(fraction)) {
					hs.add(a);
				}
			}
		} catch (UnsupportedDataTypeException e) {
			e.printStackTrace();
		}
		
		//The same for light.
		it = lightPartitions.iterator();
		
		try {
			while (it.hasNext()) {
				a = it.next();

				if (a.intersects(fraction)) {
					hs.add(a);
				}
			}
		} catch (UnsupportedDataTypeException e) {
			e.printStackTrace();
		}
		
		return hs;
	}

	/**
	 * Checks if a move is valid.
	 * 
	 * @param player The player performing the move.
	 * @param move The move as BitMatrix.
	 * 
	 * @return True, if move is valid, otherwise false.
	 * 
	 * @throws UnsupportedDataTypeException The UnsupportedDataTypeException.
	 */
	public boolean isValidMove(boolean player, BitMatrix move) throws UnsupportedDataTypeException {
		
		boolean control = false;
		
		//Passing is always allowed.
		if (move.isZeroMatrix()) {
			return true;
		}
		
		//Check if target position is empty.
		if (!move.intersects(dark) && !move.intersects(light)) {
			
			//Check if the player's group resulting from this move has at least one liberty.
			if (this.getLibertiesOfPartition(
					this.getResultingPartitionForMove(player, move)).
					getNumberOfSetBits() > 0) {
				
				control = true;
				
			} else {
				//The player's group resulting from this move has no liberties, that might be a suicide move...
				
				if (containsPartitionWithExactlyOneLiberty(
						getOpponentsAdjacentPartitionsForMove(player, move))) {
					//...but by this move, one of the opponent's partitions will lose its last liberty and
					//be captured, therefore it is valid.					
					control = true;
				} else {
					//...and none of the opponent's groups will be
					//captured, so it is a suicide move and therefore prohibited.
					control = false;	
				}				
			}
			
		} else {
			//The target position is not empty, the move is not valid.
			control = false;
		}
		
		//If the move turned out to be valid so far, the last rule to be applied is superko.
		if (control == true) {
			
			//Clone the configuration.
			Configuration newConfig = (Configuration) this.clone();

			//Perform the move for the cloned board.
			newConfig.executeMove(player, move);
			
			//Check if the move history already contains the position resulting from this move.
			if (history.contains(newConfig.getDark(), newConfig.getLight(), newConfig.getPlayersTurn())) {
				//Configuration already existed, that's a superko violation and therefore prohibited.
				control = false;
			}
		}
		
		return control;
	}
	
	/**
	 * Clears the captured nodes of the specified player.
	 * 
	 * @param player True if dark, false if light.
	 * @throws UnsupportedDataTypeException The UnsupportedDataTypeException.
	 */
	public void clearCaptured(boolean player) throws UnsupportedDataTypeException {

		Iterator<BitMatrix> it;
		
		AbstractSet<BitMatrix> hs;
		BitMatrix s;
		
		if (player) {
			hs = darkPartitions;
		} else {
			hs = lightPartitions;
		}
		
		it = hs.iterator();
		
		//Iterate the player's groups.
		while (it.hasNext()) {
			s = (BitMatrix) it.next();
			//Search for groups with zero liberties.
			if (this.getLibertiesOfPartition(s).getNumberOfSetBits() == 0) {
				
				//Increase the opponent's score.
				if (player) {
					lightsCaptured+= s.getNumberOfSetBits();
				} else {
					darksCaptured+= s.getNumberOfSetBits();
				}

				//Remove stones from the board.
				if (player) {
					dark.remove(s);
				} else {
					light.remove(s);
				}
				
				//Add partition to the clear partitions.
				clearPartitions.add(s);
								
				//Remove the captured group.
				it.remove();
			}
		}	
	}
	
	/**
	 * Gets the configuration value for the specified player.
	 * 
	 * @param player True if dark, false if light.
	 * 
	 * @return The configuration value.
	 */
	public int getConfigurationValue(boolean player) {
		int value = 0;
		
		if (!isclone) System.out.println("getConfigurationValue(player)");
		//Add the value of captured enemy stones.
		if (player) {
			value += darksCaptured;
		} else {
			value += lightsCaptured;
		}		
		
		//Remove all groups that are not alive.
		removeDeadPartitions();
		
		//Add the value of unreal and real eyes.
		value += getValueOfCapturedPartitions(player);
				
		return value;
	}
	
	/**
	 * Gets the value of the specified player's captured partitions.
	 * 
	 * @param player True if dark, false if light.
	 * @return The captured partitions' value.
	 */
	public int getValueOfCapturedPartitions(boolean player) {
		int value = 0;
		
		AbstractSet<BitMatrix> capturedPartitions, partitions;
		Iterator<BitMatrix> it1, it2;
		BitMatrix partition;
		
		
		if (player) {
			capturedPartitions = darksCapturedPartitions;
			partitions = darkPartitions;
		} else {
			capturedPartitions = lightsCapturedPartitions;
			partitions = lightPartitions;
		}
		
		//Add the value of the player's unreal eyes.
		it1 = capturedPartitions.iterator();
		
		while (it1.hasNext()) {
			value += it1.next().getNumberOfSetBits();
		}
		
		//Add the value of the player's real eyes.
		it1 = partitions.iterator();
		
		while (it1.hasNext()) {
			partition = it1.next();
			
			it2 = partition.getChildren().iterator();
			
			while (it2.hasNext()) {
				value += it2.next().getNumberOfSetBits();	
			}
		}
		
		return value;
	}
	
	/**
	 * Removes a group from the board and refreshes all sets of stones or clear partitions.
	 * 
	 * @param partition The partition as BitMatrix.
	 * @param player True if dark, false if light.
	 */
	public void removePartition(BitMatrix partition, boolean player) {
		BitMatrix stones = null, next, surroundingNodes, eye, newPartition, clearPartition;
		AbstractSet<BitMatrix> partitions = null;
		try {
			if (player) {
				stones = dark;
				partitions = darkPartitions;
				darksDeadStones += partition.getNumberOfSetBits();
			} else {
				stones = light;
				partitions = lightPartitions;
				lightsDeadStones += partition.getNumberOfSetBits();
			}
			
			//Remove partition from the stones.
			stones.remove(partition);
			
			
			//Remove partition from the player's partitions.
			Iterator<BitMatrix> it = partitions.iterator();
			next = null;
			while (it.hasNext()){
				next = it.next();
				if (next.equals(partition)) {
					it.remove();
					break;
				}
			}
			
			//Merge the clear partition with the real eyes.
			newPartition = (BitMatrix) next.clone();
			
			it = next.getChildren().iterator();
			while (it.hasNext()) {
				eye = it.next();
				it.remove();
				
				newPartition.union(eye);
			}
			
			//Merge the new partition with the surrounding clear partitions.
			surroundingNodes = BitMatrix.multiply(newPartition, adjacencies);
			
			it = clearPartitions.iterator();
			
			while (it.hasNext()) {
				clearPartition = it.next();
				
				if (clearPartition.intersects(surroundingNodes)) {
					it.remove();
					newPartition.union(clearPartition);
				}
			}
			
			//Merge the new partition with the surrounding non-real eyes.
			if (player) {
				it = darksCapturedPartitions.iterator();
			} else {
				it = lightsCapturedPartitions.iterator();
			}
			
			while (it.hasNext()) {
				eye = it.next();
				if (eye.intersects(surroundingNodes)) {
					it.remove();
					newPartition.union(eye);
				}
			}
			
			//Find out what type the new clear partition is.
			surroundingNodes = BitMatrix.multiply(newPartition, adjacencies);
			
			if (surroundingNodes.intersects(dark) && surroundingNodes.intersects(light)) {
				clearPartitions.add(newPartition);
				if (!isclone) System.out.println("Found a new clear partition: " + newPartition);
			} else {
				surroundingNodes.xor(newPartition);
				
				partitions = getPartitionsForFraction(surroundingNodes);
				
				int numberOfDarkGroups = 0;
				int numberOfLightGroups = 0;
				
				it = partitions.iterator();
				
				while (it.hasNext()) {
					partition = it.next();
					
					if (partition.intersects(dark)) {
						numberOfDarkGroups++;
					}
					if (partition.intersects(light)) {
						numberOfLightGroups++;
					}

				}
				//One of the number of groups is zero, because this is not a clear partition.
				if (numberOfDarkGroups > 0) {

					if (numberOfDarkGroups == 1) {
						//It's a real eye.
						partition.getChildren().add(newPartition);
						if (!isclone) System.out.println("Found a new dark real eye: " + newPartition);
					} else {
						//It's a non-real eye.
						darksCapturedPartitions.add(newPartition);
						if (!isclone) System.out.println("Found a new dark non-real eye: " + newPartition);
					}
				}
				if (numberOfLightGroups > 0) {
					
					if (numberOfLightGroups == 1) {
						//It's a real eye.
						partition.getChildren().add(newPartition);
						if (!isclone) System.out.println("Found a new light real eye: " + newPartition);
					} else {
						//It's a non-real eye.
						lightsCapturedPartitions.add(newPartition);
						if (!isclone) System.out.println("Found a new light non-real eye: " + newPartition);
					}
				}
				clearPartitions.add(newPartition);
			}
			
		} catch (UnsupportedDataTypeException e) {
			e.printStackTrace();
		}
	}
	

	public void removeDeadPartitions() {
		if (!isclone) System.out.println("removeDeadPartitions()");
		AbstractSet<BitMatrix> partitions;
		Iterator<BitMatrix> it, clearPartitionsIt;
		int numberOfAdjacentClearPartitions = 0, numberOfUnrealEyes = 0, numberOfRealEyes = 0;
		boolean removedGroup = true;
		//boolean removedPlayersGroup = true;
		boolean player = true;
		BitMatrix next, surroundingNodes, nextClearPartition;
		
		
		for(int i = 0; i <= 1; i++) {
			player=!player;
			removedGroup = true;
			
			if(player) {
				if (!isclone) System.out.println("getDeadPartitions(dark)");
				partitions = darkPartitions;
			} else {
				if (!isclone) System.out.println("getDeadPartitions(light)");
				partitions = lightPartitions;
			}
				
			
			
			try {
				//Start with the smallest groups.
				//for (int i = 1; i <= size*size; i++) {
				while (removedGroup) {	
					it = partitions.iterator();
					next = null;
					removedGroup = false;
					while(it.hasNext()) {
						next = it.next();
						
						if (!isclone) System.out.println("Found a group: " + next.toString());
						//A group may only be considered dead if it has less than two real eyes.
						if (next.getChildren().size() < 2) {
							if (!isclone) System.out.println("Has less than 2 real eyes.");
							//Check if the group is adjacent to non-real eyes only.			
							surroundingNodes = BitMatrix.multiply(next, adjacencies);
							
							clearPartitionsIt = clearPartitions.iterator();
							
							numberOfAdjacentClearPartitions = 0;
							numberOfUnrealEyes = 0;
							numberOfRealEyes = 0;
								
							while (clearPartitionsIt.hasNext()) {
								nextClearPartition = clearPartitionsIt.next();
								if (surroundingNodes.intersects(nextClearPartition)) {
									if (!isclone) System.out.println("Adjacent to: " + nextClearPartition);
									//Count the number of adjacent clear partitions.
									numberOfAdjacentClearPartitions++;
									
									if (player) {
										//Check if it's an unreal eye.
										if (darksCapturedPartitions.contains(nextClearPartition)
												&& nextClearPartition.getNumberOfSetBits() < 3) {
											if (!isclone) System.out.println("unreal dark eye");
											numberOfUnrealEyes++;
										}
									} else {
										//Check if it's an unreal eye.
										if (lightsCapturedPartitions.contains(nextClearPartition)) {
											if (!isclone) System.out.println("unreal light eye");
											numberOfUnrealEyes++;
										}	
									}
									//Check if it's a real eye.
									if (next.getChildren().contains(nextClearPartition)) {
										if (!isclone) System.out.println("real eye");
										numberOfRealEyes++;
									}
								}
							}
								
							//If the group is adjacent to own real or unreal eyes only,
							//the group is an own prisoner, and is therefore alive.
							/*if ((numberOfAdjacentClearPartitions - numberOfUnrealEyes - numberOfRealEyes) > 0) {
								if (!isclone) System.out.println("Is adjacent to clear partition, classified dead.");
								deadPartitions.add(next);								
							}*/
							if (numberOfUnrealEyes == 0) {
								//removePartition(next, player);
								removedGroup = true;
								break;
							}
								
							if (numberOfUnrealEyes == 1 && numberOfRealEyes == 0) {
								if (!isclone) System.out.println("Is adjacent to one unreal eye only, classified dead.");
								//removePartition(next, player);
								removedGroup = true;
								break;
							}
							
						}
						
						//If the group has at least 2 real eyes, it is alive.
					}
					
					if (removedGroup) {
						assert (next instanceof BitMatrix);
						removePartition(next, player);
					}
				}
			} catch (UnsupportedDataTypeException e) {
				e.printStackTrace();
			}
		
		}
	
	}
	
	/**
	 * Returns all possible moves the specified player can perform
	 * on the board as a BitMatrix object.
	 * 
	 * @param player The player. True if dark, false if light.
	 * 
	 * @return The regular moves.
	 */
	public BitMatrix getRegularMoves(boolean player) {
		
		//If the regular moves have already been computed for the
		//current position, getRegularMoves() behaves like a getter.
		if (regularMovesChanged) {
			BitMatrix newRegularMoves = new BitMatrix(1, getSize() * getSize());
			BitMatrix a;
			int i;
			
			try {
				//Get all unoccupied places on the board.
				newRegularMoves = BitMatrix.not(BitMatrix.xor(getDark(), getLight()));
				
				//For each unoccupied place on the board...
				for (i = 0; i < getSize()*getSize(); i++) {
					if (newRegularMoves.get(i)) {
						
						//Create a single move...
						a = new BitMatrix(1, getSize() * getSize());
						a.set(i);
						
						//...and check it out.
						if (!isValidMove(player, a)) {
							
							//If it's not valid, remove it from the BitMatrix.
							newRegularMoves.remove(a);						
						}					
					}
				}
				
			} catch (UnsupportedDataTypeException e) {
				e.printStackTrace();
			}
			
			//Replace the regularMoves BitMatrix.
			regularMoves = newRegularMoves;
			regularMovesChanged = false;
		}

		return regularMoves;	
	}
	
	public int getSize() {
		
		return size;
	}


	
	public void setSize(int size) {
	
		this.size = size;
	}


	
	public BitMatrix getAdjacencies() {
	
		return adjacencies;
	}


	
	public void setAdjacencies(BitMatrix adjacencies) {
	
		this.adjacencies = adjacencies;
	}


	
	public BitMatrix getDark() {
	
		return dark;
	}


	
	public void setDark(BitMatrix dark) {
	
		this.dark = dark;
	}


	
	public BitMatrix getLight() {
	
		return light;
	}


	
	public void setLight(BitMatrix light) {
	
		this.light = light;
	}

	public int getDarksDeadStones() {
		return darksDeadStones;
	}

	public int getLightsDeadStones() {
		return lightsDeadStones;
	}
	
	public AbstractSet<BitMatrix> getDarkPartitions() {
	
		return darkPartitions;
	}
	
	public AbstractSet<BitMatrix> getLightPartitions() {
	
		return lightPartitions;
	}
	
	public AbstractSet<BitMatrix> getClearPartitions() {
	
		return clearPartitions;
	}
	
	public boolean getPlayersTurn() {
	
		return playersTurn;
	}


	
	private void changePlayersTurn() {
		this.playersTurn = !playersTurn;
	}
	
	public int getDarksCaptured() {
		
		return darksCaptured;
	}
	
	public int getLightsCaptured() {
	
		return lightsCaptured;
	}
	
	public AbstractSet<BitMatrix> getDarksCapturedPartitions() {
		
		return darksCapturedPartitions;
	}
	
	public AbstractSet<BitMatrix> getLightsCapturedPartitions() {
	
		return lightsCapturedPartitions;
	}
	
	/**
	 * @return the history
	 */
	public PositionTable getHistory() {
		return history;
	}

	/**
	 * @param history the history to set
	 */
	public void setHistory(PositionTable history) {
		this.history = history;
	}
	
	/* (non-Javadoc)
	 * @see java.lang.Object#clone()
	 */
	public Object clone() {
		
		/*if (logger.isInfoEnabled()) {
			logger.info("Configuration cloned.");
		}*/
		Iterator<BitMatrix> it;
		Configuration newConfig = new Configuration(size);
		
		newConfig.setDark((BitMatrix) this.dark.clone());
		newConfig.setLight((BitMatrix) this.light.clone());
		
		it = this.darkPartitions.iterator();
		
		while (it.hasNext()) {
			newConfig.darkPartitions.add((BitMatrix) it.next().clone());
		}
		
		it = this.lightPartitions.iterator();
		
		while (it.hasNext()) {
			newConfig.lightPartitions.add((BitMatrix) it.next().clone());
		}
		
		newConfig.clearPartitions.clear();
		it = this.clearPartitions.iterator();
		
		while (it.hasNext()) {
			newConfig.clearPartitions.add((BitMatrix) it.next().clone());
		}		
		
		it = this.darksCapturedPartitions.iterator();
		
		while (it.hasNext()) {
			newConfig.darksCapturedPartitions.add((BitMatrix) it.next().clone());
		}
		
		it = this.lightsCapturedPartitions.iterator();
		
		while (it.hasNext()) {
			newConfig.lightsCapturedPartitions.add((BitMatrix) it.next().clone());
		}
				
		if (!this.getPlayersTurn()) {
			newConfig.changePlayersTurn();
		}
		
		newConfig.darksCaptured = this.darksCaptured;
		newConfig.lightsCaptured = this.lightsCaptured;
		
		newConfig.regularMoves = (BitMatrix) this.regularMoves.clone();
		newConfig.regularMovesChanged = this.regularMovesChanged;
		
		newConfig.history = (PositionTable) this.history.clone();
		
		newConfig.isclone = true;
		
		return newConfig;
	}	
}
